#!/depot/perl-5.6.1/bin/perl

############################################################
# Title : 9*9 Matrix Solving
#-----------------------------------------------------------
# By    : Sean Zhang
# At    : Dec, 2005
# @     : szhang@synopsys.com
############################################################

use Data::Dumper;

my @matrix= init($ARGV[0]);

print "Problem matrix:\n";
print_matrix();

my $cnt = 1;
while(1){
    my $done = do_it();
    last if $done == 1 || $cnt >= 20;;
    $cnt++;
}
print "\n\n";
print "After $cnt times iteration:\n";
print_matrix();
exit(0);

#-------------------------------------------------------------
#-------------------------------------------------------------

sub do_it{
    my $done = 1;
    for(my $i=0;$i<9;$i++){
	for(my $j=0;$j<9;$j++){
	    check_it(\@matrix,$i,$j);
	    fill_it(\@matrix,$i,$j);
            $done = 0 if $matrix[$i][$j][0] eq 'x';
	}
    }
    return $done;
}

sub print_matrix {
    print '+-------------+-------------+-------------+',"\n";
    for(my $i=0;$i<9;$i++){
	for(my $j=0;$j<9;$j++){
            print "| " if($j==0);
            my $v = $matrix[$i][$j][0];
            my $vf = $matrix[$i][$j][10];
            if($vf eq 'Y'){
		print " $v  "; 
            }else{
		print "[$v] "; 
            }
            print "| " if($j%3==2);
	}
        print "\n";
	print '+-------------+-------------+-------------+',"\n" if $i%3==2;
    }

}

sub check_it{
    my ($matrix,$i,$j) = @_;
    my $row  = $matrix->[$i];
    my $col  = $matrix->[$i];
    my $cell = $matrix->[$i][$j];
    foreach my $k (0..8){
       my $v1 = $matrix->[$i][$k][0];
       my $v2 = $matrix->[$k][$j][0];
       if($k != $j && $v1 ne 'x'){
           $cell->[$v1] = 'x';
       }
       if($k != $i && $v2 ne 'x'){
           $cell->[$v2] = 'x';
       }
    }# end search row and column

    my $ii = int($i/3) ;
    my $ji = int($j/3) ;
    my $cc_i = $ii*3 + 1;
    my $cc_j = $ji*3 + 1;
    for(my $ki = $cc_i - 1; $ki <= $cc_i + 1; $ki++){
	for(my $kj = $cc_j - 1; $kj <= $cc_j + 1; $kj++){
           next if $ki == $i && $kj == $j;
	   my $v = $matrix->[$ki][$kj][0];
	   if($v ne 'x'){
	       $cell->[$v] = 'x';
	   }
        }
    }# end search box
}

sub debug {
    local $_ = shift;
    return;
    print "DEBUG: ",$_, "\n";
}
sub fill_it{
    my ($matrix,$i,$j) = @_;
    my $row  = $matrix->[$i];
    my $col  = $matrix->[$i];
    my $cell = $matrix->[$i][$j];
    debug("\$matrix[$i][$j] = ".join(" ",@$cell));
    debug("\$matrix[$i][$j+1] = ".join(" ",@{$matrix->[$i][$j+1]}));
    return if $cell->[0] ne 'x' ;
    my $possible   = 0;
    my $possible_i = 0;
    # search cell itself
    foreach my $k (1..9){
       if($cell->[$k] ne 'x'){
           $possible ++;
	   $possible_i = $k;
           debug("self : $k $possible");
           my $p = check_other($matrix,$i,$j,$k);
           if($p){
	       $cell->[0] = $k ;
	       return;
           }
       }
    }# end search row and column
    if($possible == 1){
        $cell->[0] = $possible_i;
        return;
    }

    
}

sub check_other{
    my ($matrix,$i,$j,$value) = @_;
    my $cnt_row = 0;
    my $cnt_col = 0;
    my $cnt_box = 0;

    foreach my $k (0..8){
       my $v1 = $matrix->[$i][$k][0];
       my $v2 = $matrix->[$k][$j][0];
       if($k != $j){
           if($v1 ne 'x'){
	       $cnt_row ++  if $v1 == $value
           }else{
               $cnt_row ++  if $matrix->[$i][$k][$value] ne 'x';
           }
       }
       if($k != $i){
           if($v2 ne 'x'){
	       $cnt_col ++  if $v2 == $value
           }else{
               $cnt_col ++  if $matrix->[$k][$j][$value] ne 'x';
           }
       }
    }# end search row and column

    my $ii = int($i/3) ;
    my $ji = int($j/3) ;
    my $cc_i = $ii*3 + 1;
    my $cc_j = $ji*3 + 1;
    debug("cc_i = $cc_i   cc_j = $cc_j");
    for(my $ki = $cc_i - 1; $ki <= $cc_i + 1; $ki++){
	for(my $kj = $cc_j - 1; $kj <= $cc_j + 1; $kj++){
           next if $ki == $i && $kj == $j;
	   my $v = $matrix->[$ki][$kj][0];
	   if($v ne 'x'){
               $cnt_box ++  if $v == $value ;
	   }else{
               $cnt_box ++  if $matrix->[$ki][$kj][$value] ne 'x';
           }
        }
    }# end search box
    debug("cnt_row = $cnt_row || cnt_col = $cnt_col || cnt_box = $cnt_box");
    return $cnt_row == 0 || $cnt_col == 0 || $cnt_box==0;
}

sub init{
    my $file = shift;
    
    my @matrix = ();
    my $fp = \*DATA;
    if(defined($file)){
        open(F,$file) || die "Error: can not open file <$file>. $!\n";
        $fp = \*F;
    }
    while(<$fp>){
        next if /^\s*$/;
        my @toks = split(/\s+/,$_);
        for(my $i=0;$i<9;$i++){
            $toks[$i] = [$toks[$i],1..9];
            if($toks[$i]->[0] ne 'x'){
               foreach my $f (1..9){
                   $toks[$i]->[$f] = 'x';
               }
               $toks[$i]->[$toks[$i]->[0]] = 1;
               $toks[$i]->[10] = 'Y';
            }
        }
        push @matrix, \@toks;
    }
    close($fp);
    return @matrix;
}

__DATA__
4	x	x	x	7	x	x	x	2
x	8	x	x	x	x	x	1	x
x	x	x	9	3	5	x	x	x
x	x	7	x	x	x	5	x	x
5	x	4	x	9	x	6	x	3
x	x	8	x	x	x	2	x	x
x	x	x	8	5	3	x	x	x
x	5	x	x	x	x	x	3	x
9	x	x       x	4	x	x       x	7



Problem matrix:
+-------------+-------------+-------------+
| [x]  1  [x] |  3  [x] [x] | [x]  6  [x] |
|  5   9   6  | [x]  7  [x] |  4   3  [x] |
| [x] [x] [x] | [x] [x]  4  | [x]  8  [x] |
+-------------+-------------+-------------+
| [x] [x]  1  | [x] [x] [x] | [x] [x]  8  |
| [x]  6  [x] | [x] [x] [x] | [x]  2  [x] |
|  2  [x] [x] | [x] [x] [x] |  5  [x] [x] |
+-------------+-------------+-------------+
| [x]  3  [x] |  4  [x] [x] | [x] [x] [x] |
| [x]  4   2  | [x]  6  [x] |  8   9   1  |
| [x]  5  [x] | [x] [x]  1  | [x]  7  [x] |
+-------------+-------------+-------------+


After 5 times iteration:
+-------------+-------------+-------------+
| [8]  1  [4] |  3  [5] [2] | [9]  6  [7] |
|  5   9   6  | [1]  7  [8] |  4   3  [2] |
| [3] [2] [7] | [6] [9]  4  | [1]  8  [5] |
+-------------+-------------+-------------+
| [9] [7]  1  | [2] [3] [5] | [6] [4]  8  |
| [4]  6  [5] | [8] [1] [9] | [7]  2  [3] |
|  2  [8] [3] | [7] [4] [6] |  5  [1] [9] |
+-------------+-------------+-------------+
| [1]  3  [9] |  4  [8] [7] | [2] [5] [6] |
| [7]  4   2  | [5]  6  [3] |  8   9   1  |
| [6]  5  [8] | [9] [2]  1  | [3]  7  [4] |
+-------------+-------------+-------------+

